package leetcode;


import java.util.*;

public class CheckInclusion {
    boolean result = false;

    public static void main(String[] args) {
        CheckInclusion checkInclusion = new CheckInclusion();
        boolean b = checkInclusion.checkInclusion("abaa", "eidabaaadadaooo");
        System.out.println(b);
    }

    public boolean checkInclusion1(String s1, String s2) {
        char[] chars1 = s1.toCharArray();
        Arrays.sort(chars1);
        int n1 = s1.length();
        int n2 = s2.length();
        if (n2 < n1) {
            return false;
        }
        int index = 0;
        for (int i = n1; i <= n2; i++) {
            String substring = s2.substring(index++, i);
            char[] chars = substring.toCharArray();
            Arrays.sort(chars);
            boolean equals = Arrays.equals(chars, chars1);
            if (equals){
                return true;
            }
        }
        return false;
    }


    public boolean checkInclusion(String s1, String s2) {
        Set<String> set = new HashSet<>();
        int n1 = s1.length();
        int n2 = s2.length();
        if (n2 < n1) {
            return false;
        }
        int index = 0;
        for (int i = n1; i <= n2; i++) {
            set.add(s2.substring(index, i));
            index++;
        }
        char[] chars = s1.toCharArray();
        dfs(chars, set, new ArrayList<Character>(n1), new boolean[n1], 0);
        return result;
    }

    public void dfs(char[] char1, Set<String> set, List<Character> path, boolean[] isVisit, int k) {
        if (result) {
            return;
        }
        if (k == char1.length) {
            StringBuilder s = new StringBuilder();
            for (Character character:path){
                s.append(character);
            }
            String s1 = s.toString();
            if (set.contains(s1)) {
                result = true;
            }
        } else {
            for (int i = 0; i < char1.length; i++) {
                if (!isVisit[i]) {
                    path.add(char1[i]);
                    isVisit[i] = true;
                    dfs(char1, set, path, isVisit, k + 1);
                    isVisit[i] = false;
                    path.remove(path.size()-1);
                }
            }
        }
    }
}
